package com.future;

/**
 * Description: 518. ��Ǯ�һ� II (ͬ���� 322. ��Ǯ�һ� )
 * ����һ���������� coins ��ʾ��ͬ����Ӳ�ң����һ������ amount ��ʾ�ܽ�
 * <p>
 * ������㲢���ؿ��Դճ��ܽ���Ӳ�������������κ�Ӳ����϶��޷��ճ��ܽ����� 0 ��
 * <p>
 * ����ÿһ������Ӳ�������޸���?
 * <p>
 * ��Ŀ���ݱ�֤������� 32 λ������������
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺amount = 5, coins = [1, 2, 5]
 * �����4
 * ���ͣ������ַ�ʽ���Դճ��ܽ�
 * 5=5
 * 5=2+2+1
 * 5=2+1+1+1
 * 5=1+1+1+1+1
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode.cn/problems/coin-change-2
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/12 11:14
 */
public class Solution_518 {

    public static void main(String[] args) {
        int amount = 5;
        int[] coins = {1, 2, 5};
      /*  amount = 3;
        coins = new int[]{2};*/
        System.out.println(change(amount, coins));
        System.out.println(change_dp(amount, coins));
    }

    public static int change_dp(int amount, int[] coins) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        int N = coins.length;
        /**
         * dp[i][j]����ʾ��0...i,��ʣ��j�����Ҫ�һ�
         */
        int[][] dp = new int[N + 1][amount + 1];
        dp[N][0] = 1;
        for (int rest = 1; rest < amount + 1; rest++) {
            /**
             * rest������Ϊ��amountʣ��
             */
            dp[N][rest] = 0;
        }
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest < amount + 1; rest++) {
                int ans = 0;
                for (int zhang = 0; zhang * coins[index] <= rest; zhang++) {
                    ans += dp[index + 1][rest - zhang * coins[index]];
                }
                dp[index][rest] = ans;
            }
        }
        int ans = dp[0][amount];
        return ans;
    }


    // ================��һ�汾==================

    /**
     * ��������ʱ��
     *
     * @param amount
     * @param coins
     * @return
     */
    public static int change(int amount, int[] coins) {
        if (coins == null || coins.length == 0) {
            return -1;
        }
        return process(coins, 0, amount);
    }

    private static int process(int[] coins, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }
        int ans = 0;
        for (int zhang = 0; zhang * coins[index] <= rest; zhang++) {
            ans += process(coins, index + 1, rest - zhang * coins[index]);
        }
        return ans;
    }


}
